def read_grammar(filename):
    """读取文法文件"""
    try:
        with open(filename, 'r', encoding='utf-8') as f:
            lines = [line.strip() for line in f.readlines() if line.strip()]
    except FileNotFoundError:
        raise Exception(f"找不到文件 {filename}")
    
    grammar = {}
    start_symbol = None
    terminals = set()
    non_terminals = set()
    
    # 解析文法
    for line in lines[:-1]:  # 最后一行是目标字符串（如果有的话）
        # 处理产生式格式（支持 -> 或 →）
        if '->' in line:
            lhs, rhs = line.split('->')
        elif '→' in line:
            lhs, rhs = line.split('→')
        else:
            lhs, rhs = line[0], line[1:]  # 默认第一个字符为非终结符
        
        lhs = lhs.strip()
        rhs = rhs.strip()

        # 设置开始符号（第一个出现的非终结符）
        if not start_symbol:
            start_symbol = lhs[0] if lhs[0].isupper() else None

        # 记录非终结符和终结符
        for char in lhs:
            if char.isupper():
                non_terminals.add(char)
        for char in rhs:
            if char.islower() or char.isdigit():
                terminals.add(char)
            elif char.isupper():
                non_terminals.add(char)

        # 存储产生式
        if lhs not in grammar:
            grammar[lhs] = []
        grammar[lhs].append(rhs)
    
    target_string = lines[-1] if lines else ""
    
    return grammar, start_symbol, list(terminals), list(non_terminals), target_string

def classify_grammar(grammar):
    """对文法进行分类"""
    is_type_1 = True
    is_type_2 = True
    is_type_3 = True
    
    right_linear = True
    left_linear = True

    for lhs, rhs_list in grammar.items():
        for rhs in rhs_list:
            # 处理空串表示方式
            rhs_clean = rhs.strip()
            is_epsilon = rhs_clean in ('ε', 'e')

            # 类型1检查: |α| ≤ |β|
            if len(lhs) > len(rhs) and not is_epsilon:
                is_type_1 = False
            
            # 类型2检查: 左边必须只有一个非终结符
            if len(lhs) != 1 or not lhs[0].isupper():
                is_type_2 = False

            # 类型3检查（前提必须是类型2）
            if is_type_2:
                if len(rhs) == 1:
                    if rhs[0].islower() or rhs[0].isdigit() or is_epsilon:
                        # 可以是终结符或空串
                        pass
                    else:
                        is_type_3 = False
                elif len(rhs) == 2:
                    # 右线性：A → aB
                    if ((rhs[0].islower() or rhs[0].isdigit()) and rhs[1].isupper()):
                        left_linear = False  # 不再认为是左线性
                    # 左线性：A → Ba
                    elif ((rhs[1].islower() or rhs[1].isdigit()) and rhs[0].isupper()):
                        right_linear = False  # 不再认为是右线性
                    else:
                        is_type_3 = False
                elif len(rhs) == 0 or is_epsilon:
                    # 空串允许存在
                    pass
                else:
                    is_type_3 = False

    if is_type_3 and (left_linear or right_linear):
        return 3
    elif is_type_2:
        return 2
    elif is_type_1:
        return 1
    else:
        return 0


def derive_string(grammar, start_symbol, target_string):
    """尝试推导出目标字符串（DFS）"""
    def helper(current, path):
        if current == target_string:
            return path + [current]
        if len(current) > len(target_string):  # 剪枝
            return None
        for i in range(len(current)):
            if current[i] in non_terminals:
                for prod in grammar.get(current[i], []):
                    new_str = current[:i] + prod + current[i+1:]
                    result = helper(new_str, path + [current])
                    if result:
                        return result
        return None

    non_terminals = set()
    for lhs in grammar.keys():
        non_terminals.update(lhs)

    derivation = helper(start_symbol, [])
    return derivation



def main():
    filename = "g.in"
    
    # 读取并解析文法
    try:
        grammar, start_symbol, _, _, target_string = read_grammar(filename)
    except Exception as e:
        print(f"错误：无法读取或解析文法文件 - {str(e)}")
        return

    # 分类文法
    grammar_type = classify_grammar(grammar)
    type_names = {0: "0型", 1: "1型", 2: "2型", 3: "3型"}
    print(f"该文法是{type_names.get(grammar_type, '未知类型')}文法")

    # 如果是3型文法，则尝试推导给定字符串
    if grammar_type == 3:
        print(f"\n正在尝试用3型文法推导字符串 '{target_string}'...")
        derivation = derive_string(grammar, start_symbol, target_string)

        if derivation:
            print("推导过程:")
            for i, step in enumerate(derivation):
                print(step, end=" => " if i < len(derivation) - 1 else "\n")
            print(f"\n✅ 成功推导出目标字符串 '{target_string}'")
        else:
            print(f"\n❌ 无法推导出目标字符串 '{target_string}'")
    else:
        print("\n⚠️ 当前文法不是3型文法，跳过字符串推导部分")


if __name__ == "__main__":
    main()
